/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/binary-search-tree-iterator
   @Language: C++
   @Datetime: 16-02-09 08:53
   */

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 * Example of iterate a tree:
 * BSTIterator iterator = BSTIterator(root);
 * while (iterator.hasNext()) {
 *    TreeNode * node = iterator.next();
 *    do something for node
 */
class BSTIterator {
	stack<TreeNode*> s;
	void prepose(TreeNode *rt){
		for(; rt; rt=rt->left)
			s.push(rt);
	}

public:
	//@param root: The root of binary tree.
	BSTIterator(TreeNode *root) {
		// write your code here
		for(; s.size(); s.pop());
		prepose(root);
	}

	//@return: True if there has next node, or false
	bool hasNext() {
		// write your code here
		return s.size();
	}

	//@return: return next node
	TreeNode* next() {
		// write your code here
		if (!hasNext()) return NULL;
		TreeNode *ans = s.top();
		s.pop();
		prepose(ans->right);
		return ans;
	}
};
